Hvorfor behandler et sorteret array hurtigere end behandling af et usorteret array?

Du er offer for gren forudsigelse mislykkes.
Hvad er brancheforudsigelse?
Overvej et jernbanekryds:
Billede af Mecanismo via Wikimedia Commons. Brugt under CC-By-SA 3.0-licensen.
Forestil dig for argumentets skyld, at dette er tilbage i 1800'erne - før langdistance eller radiokommunikation.
Du er operatør for et kryds, og du hører et tog komme. Du har ingen idé om, hvilken vej det skal gå. Du stopper toget for at spørge chaufføren, hvilken retning de vil have. Og så indstiller du kontakten korrekt.
Togene er tunge og har en masse inerti. Så det tager for evigt at starte op og sænke farten.
Er der en bedre måde? Du gætter på hvilken retning toget kører!
Hvis du gættede rigtigt, fortsætter det.
Hvis du gætter forkert, stopper kaptajnen, sikkerhedskopierer og råber på dig for at vende kontakten. Derefter kan den genstarte den anden sti.
Hvis du gætter rigtigt hver gang, behøver toget aldrig at stoppe. Hvis du gætter forkert for ofte, bruger toget meget tid på at stoppe, sikkerhedskopiere og genstarte.
Overvej en if-sætning: På processorniveau er det en greninstruktion:
Du er en processor, og du ser en gren. Du har ingen idé om, hvilken vej det vil gå. Hvad laver du? Du standser udførelsen og venter, indtil de tidligere instruktioner er færdige. Derefter fortsætter du ned ad den korrekte sti.
Moderne processorer er komplicerede og har lange rørledninger. Så de tager for evigt at "varme op" og "bremse ned".
Er der en bedre måde? Du gætter på hvilken retning grenen vil gå!
Hvis du gættede rigtigt, fortsætter du med at udføre.
Hvis du gætter forkert, skal du skylle rørledningen og rulle tilbage til grenen. Derefter kan du genstarte den anden sti.
Hvis du gætter rigtigt hver gang, behøver udførelsen aldrig at stoppe. Hvis du gætter forkert for ofte, bruger du meget tid på at stoppe, rulle tilbage og genstarte.
Dette er gren forudsigelse. Jeg indrømmer, at det ikke er den bedste analogi, da toget bare kunne signalere retningen med et flag. Men på computere ved processoren ikke, hvilken retning en filial vil gå indtil sidste øjeblik.
Så hvordan vil du strategisk gætte for at minimere antallet af gange, som toget skal sikkerhedskopiere og gå ned ad den anden sti? Du ser på fortidens historie! Hvis toget går til venstre 99% af tiden, gætter du på venstre. Hvis det skifter, skifter du dine gæt. Hvis det går en vej hver tredje gang, gætter du det samme ...
Med andre ord forsøger du at identificere et mønster og følge det. Dette er mere eller mindre, hvordan grenprædiktorer fungerer.
De fleste applikationer har velopdragne grene. Så moderne grenprædiktorer vil typisk opnå> 90% hitrate. Men når vi står over for uforudsigelige grene uden genkendelige mønstre, er grenprædiktorer praktisk talt ubrugelige.
Yderligere læsning: "Branchprediktor" -artikel på Wikipedia.
Som antydet ovenfra er synderen denne if-sætning:
hvis (data [c]> = 128)
sum + = data [c];
Bemærk, at dataene fordeles jævnt mellem 0 og 255. Når dataene sorteres, vil omtrent den første halvdel af gentagelserne ikke komme ind i if-sætningen. Derefter indtaster de alle if-erklæringen.
Dette er meget venligt for grenprædiktoren, da filialen fortløbende går i samme retning mange gange. Selv en simpel mættetæller forudsiger grenen korrekt bortset fra de få iterationer, efter at den skifter retning.
Hurtig visualisering:
T = gren taget
N = gren ikke taget
data [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
gren = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNTTTTTTTTT ... TTTTTTTTTT (let at forudsige)
Men når dataene er helt tilfældige, bliver grenprædiktoren ubrugelig, fordi den ikke kan forudsige tilfældige data. Således vil der sandsynligvis være omkring 50% forkert forudsigelse (ikke bedre end tilfældigt gætte).
data [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
gren = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (helt tilfældigt - svært at forudsige)
Så hvad kan man gøre?
Hvis compileren ikke er i stand til at optimere grenen til et betinget træk, kan du prøve nogle hacks, hvis du er villig til at ofre læsbarhed for ydeevne.
Erstatte:
hvis (data [c]> = 128)
sum + = data [c];
med:
int t = (data [c] - 128) >> 31;
sum + = ~ t & data [c];
Dette eliminerer grenen og erstatter den med nogle bitvise operationer.
(Bemærk, at dette hack ikke nøjagtigt svarer til den oprindelige if-sætning. Men i dette tilfælde er det gyldigt for alle inputværdierne for data [].)
Benchmarks: Core i7 920 @ 3,5 GHz
C ++ - Visual Studio 2010 - x64-udgivelse
// Filial - Tilfældig
sekunder = 11,777
// Filial - sorteret
sekunder = 2.352
// Grenløs - tilfældig
sekunder = 2.564
// Grenfri - sorteret
sekunder = 2,587
Java - NetBeans 7.1.1 JDK 7 - x64
// Filial - Tilfældig
sekunder = 10,93293813
// Filial - sorteret
sekunder = 5,643797077
// grenløs -Tilfældig
sekunder = 3.113581453
// Grenfri - sorteret
sekunder = 3.186068823
Bemærkninger:
Med filialen: Der er en enorm forskel mellem de sorterede og usorterede data.
Med hacket: Der er ingen forskel mellem sorterede og usorterede data.
I C ++ tilfælde er hacket faktisk en smule langsommere end med grenen, når dataene sorteres.
En generel tommelfingerregel er at undgå dataafhængig forgrening i kritiske sløjfer (som i dette eksempel).
Opdatering:
GCC 4.6.1 med -O3 eller -ftree-vectorize på x64 er i stand til at generere et betinget træk. Så der er ingen forskel mellem de sorterede og usorterede data - begge er hurtige.
(Eller noget hurtigt: i den allerede sorterede sag kan cmov være langsommere, især hvis GCC sætter den på den kritiske sti i stedet for bare at tilføje, især på Intel før Broadwell, hvor cmov har 2 cyklus latenstid: gcc optimeringsflag -O3 gør koden langsommere end -O2)
VC ++ 2010 er ikke i stand til at generere betingede træk for denne gren, selv under / Ox.
Intel C ++ Compiler (ICC) 11 gør noget mirakuløst. Den skifter de to løkker ud og løfter den uforudsigelige gren til den ydre løkke. Så det er ikke kun immunt mod misforudsigelserne, det er også dobbelt så hurtigt som hvad VC ++ og GCC kan generere! Med andre ord udnyttede ICC test-loop til at besejre benchmark ...
Hvis du giver Intel-kompilatoren den grenløse kode, vektoriserer den bare højre ud ... og er lige så hurtig som med grenen (med loop-udvekslingen).
Dette viser, at selv modne moderne compilere kan variere vildt i deres evne til at optimere kode ...
|
Gren forudsigelse.
Med en sorteret matrix er betingelsesdataene [c]> = 128 først falske for en række værdier og bliver derefter sande for alle senere værdier. Det er let at forudsige. Med et usorteret array betaler du forgreningsomkostningerne.
|
Årsagen til, at ydeevnen forbedres drastisk, når dataene sorteres, er, at grenforudsigelsesstraffen fjernes, som forklaret smukt i Mysticials svar.
Nu, hvis vi ser på koden
hvis (data [c]> = 128)
sum + = data [c];
vi kan finde ud af, at betydningen af ​​denne særlige, hvis ... ellers ... gren er at tilføje noget, når en betingelse er opfyldt. Denne type gren kan let omdannes til en betinget flytningserklæring, som vil blive samlet til en betinget flytningsinstruktion: cmovl, i et x86-system. Filialen og dermed den potentielle grenforudsigelsesstraf fjernes.
I C, således C ++, er udsagnet, som ville kompilere direkte (uden nogen optimering) i den betingede flytningsinstruktion i x86, den ternære operatør ...? ...: .... Så vi omskriver ovenstående udsagn til en tilsvarende:
sum + = data [c]> = 128? data [c]: 0;
Mens vi opretholder læsbarhed, kan vi kontrollere hastighedsfaktoren.
På en Intel Core i7-2600K @ 3,4 GHz og frigivelsestilstand for Visual Studio 2010 er benchmarket (format kopieret fra Mysticial):
x86
// Filial - Tilfældig
sekunder = 8,885
// Filial - sorteret
sekunder = 1,528
// Grenløs - tilfældig
sekunder = 3.716
// Grenfri - sorteret
sekunder = 3,71
x64
// Filial - Tilfældig
sekunder = 11.302
// Filial - sorteret
sekunder = 1.830
// Grenløs - tilfældig
sekunder = 2.736
// Grenfri - sorteret
sekunder = 2.737
Resultatet er robust i flere tests. Vi får en hurtig hastighed, når grenresultatet er uforudsigeligt, men vi lider lidt, når det er forudsigeligt. Faktisk er ydeevnen den samme uanset datamønsteret, når du bruger et betinget træk.
Lad os nu se nærmere på ved at undersøge den x86-samling, de genererer. For enkelheds skyld bruger vi to funktioner max1 og max2.
max1 bruger den betingede gren, hvis ... ellers ...:
int max1 (int a, int b) {
hvis (a> b)
returnere en;
andet
returnere b;
}
max2 bruger den ternære operatør ...? ...: ...:
int max2 (int a, int b) {
returnere a> b? a: b;
}
På en x86-64 maskine genererer GCC -S samlingen nedenfor.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp .L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
forlade
ret
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
forlade
ret
max2 bruger meget mindre kode på grund af brugen af ​​instruktion cmovge. Men den virkelige gevinst er, at max2 ikke involverer grenhopp, jmp, som ville have en betydelig præstationsstraff, hvis det forudsagte resultat ikke er korrekt.
Så hvorfor fungerer et betinget træk bedre?
I en typisk x86-processor er udførelsen af ​​en instruktion opdelt i flere faser. Groft har vi forskellige hardware til at håndtere forskellige faser. Så vi behøver ikke vente på, at en instruktion er færdig med at starte en ny. Dette kaldes rørledning.
I en forgreningssag bestemmes følgende instruktion af den foregående, så vi kan ikke foretage rørledning. Vi må enten vente eller forudsige.
I en betinget flytninginstruktionen til udførelse af betinget flytning er opdelt i flere faser, men de tidligere faser som Fetch og Decode afhænger ikke af resultatet af den tidligere instruktion; kun sidstnævnte faser har brug for resultatet. Således venter vi en brøkdel af en instruktions udførelsestid. Dette er grunden til, at den betingede flytningsversion er langsommere end grenen, når forudsigelsen er let.
Bogen Computer Systems: A Programmer's Perspective, anden udgave forklarer dette detaljeret. Du kan tjekke afsnit 3.6.6 for instruktioner om betinget flytning, hele kapitel 4 for processorarkitektur og afsnit 5.11.2 for speciel behandling af grenforudsigelses- og misforudsigelsesstraffe.
Nogle gange kan nogle moderne compilere optimere vores kode til samling med bedre ydeevne, nogle gange kan nogle compilers ikke (den pågældende kode bruger Visual Studios oprindelige compiler). At vide præstationsforskellen mellem en gren og et betinget træk, når det er uforudsigeligt, kan hjælpe os med at skrive kode med bedre ydeevne, når scenariet bliver så komplekst, at compileren ikke kan optimere dem automatisk.
|
Hvis du er nysgerrig efter endnu flere optimeringer, der kan gøres med denne kode, skal du overveje dette:
Startende med den originale sløjfe:
for (usigneret i = 0; i <100000; ++ i)
{
for (usigneret j = 0; j  = 128)
sum + = data [j];
}
}
Med loop-udveksling kan vi sikkert ændre denne loop til:
for (usigneret j = 0; j  = 128)
sum + = data [j];
}
}
Derefter kan du se, at hvis betinget er konstant under hele udførelsen af ​​i-sløjfen, så du kan hejse hvis ud:
for (usigneret j = 0; j  = 128)
{
for (usigneret i = 0; i <100000; ++ i)
{
sum + = data [j];
}
}
}
Derefter ser du, at den indre sløjfe kan kollapses i et enkelt udtryk, forudsat at flydepunktsmodellen tillader det (/ fp: hurtigt kastes f.eks.)
for (usigneret j = 0; j  = 128)
{
sum + = data [j] * 100000;
}
}
Den ene er 100.000 gange hurtigere end før.
|
Ingen af ​​os vil uden tvivl være interesseret i måder at identificere kode, der er problematisk for CPU's gren-forudsigelse. Valgrind-værktøjets cachegrind har en gren-forudsigelsessimulator aktiveret ved hjælp af --branch-sim = ja-flag. At køre det over eksemplerne i dette spørgsmål, med antallet af ydre sløjfer reduceret til 10000 og kompileret med g ++, giver disse resultater:
Sorteret:
== 32551 == Filialer: 656.645.130 (656.609.208 cond + 35.922 ind)
== 32551 == Fejlagtige forudsigelser: 169.556 (169.095 cond + 461 ind)
== 32551 == Mispred rate: 0,0% (0,0% + 1,2%)
Usorteret:
== 32555 == Filialer: 655.996.082 (655.960.160 cond + 35.922 ind)
== 32555 == Fejlagtige forudsigelser: 164.073.152 (164.072.692 cond + 460 ind)
== 32555 == Forkert sats: 25,0% (25,0% + 1,2%)
Boring ned i linje-for-linje output produceret af cg_annotate ser vi for den pågældende løkke:
Sorteret:
Bc Bcm Bi Bim
10,001 4 0 0 for (usigneret i = 0; i <10000; ++ i)
. . . . {
. . . . // primær sløjfe
327.690.000 10.016 0 0 for (usigneret c = 0; c  = 128)
0 0 0 0 sum + = data [c];
. . . . }
. . . . }
Usorteret:
Bc Bcm Bi Bim
10,001 4 0 0 for (usigneret i = 0; i <10000; ++ i)
. . . . {
. . . . // primær sløjfe
327.690.000 10.038 0 0 for (usigneret c = 0; c  = 128)
0 0 0 0 sum + = data [c];
. . . . }
. . . . }
Dette giver dig mulighed for let at identificere den problematiske linje - i den usorterede version, hvis (data [c]> = 128) linjen forårsager 164.050.007 forkert forudsagte betingede grene (Bcm) under cachegrinds gren-forudsigelsesmodel, hvorimod den kun forårsager 10,006 i den sorterede version .
Alternativt kan du på Linux bruge subsystemet Performance Counter til at udføre den samme opgave, men med native performance ved hjælp af CPU-tællere.
perf stat ./sumtest_sorted
Sorteret:
Statistik over præstationstællere for './sumtest_sorted':
11808.095776 task-ur # 0.998 CPU'er brugt
1.062 kontekstafbrydere # 0,090 K / sek
14 CPU-migreringer # 0,001 K / sek
337 sidefejl # 0,029 K / sek
26.487.882.764 cyklusser # 2.243 GHz
41.025.654.322 instruktioner # 1.55 insns pr. Cyklus
6.558.871.379 grene # 555.455 M / sek
567.204 filial-savner # 0,01% af alle filialer
11.827228330 forløbet sekunder
Usorteret:
Ydeevnemodstatistik for './sumtest_unsorted':
28877.954344 task-ur # 0.998 CPU'er brugt
2.584 kontekstafbrydere # 0,089 K / sek
18 CPU-migreringer # 0,001 K / sek
335 sidefejl # 0,012 K / sek
65.076.127.595 cyklusser # 2.253 GHz
41.032.528.741 instruktioner # 0.63 insns pr. Cyklus
6.560.579.013 filialer # 227.183 M / sek
1.646.394.749 filial-savner # 25.10% af alle filialer
28.935500947 forløbet tid
Det kan også udføre kildekodeannotering med adskillelse.
perf record -e branch-misses ./sumtest_unsorted
perfekt annotere -d sumtest_unsorted
Procent | Kildekode og adskillelse af sumtest_unsorted
------------------------------------------------
...
: sum + = data [c];
0,00: 400a1a: mov -0x14 (% rbp),% eax
39.97: 400a1d: mov% eax,% eax
5.31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4,60: 400a26: cltq
0,00: 400a28: tilføj% rax, -0x30 (% rbp)
...
Se performance tutorial for flere detaljer.
|
Jeg har lige læst om dette spørgsmål og dets svar, og jeg føler, at der mangler et svar.
En almindelig måde at eliminere forudsigelse på gren, som jeg har fundet ud af at fungere særlig godt på administrerede sprog, er en tabelopslag i stedet for at bruge en gren (selvom jeg ikke har testet det i dette tilfælde).
Denne tilgang fungerer generelt, hvis:
det er et lille bord og sandsynligvis cache i processoren, og
du kører ting i en ret tæt loop, og / eller processoren kan forudindlæse dataene.
Baggrund og hvorfor
Fra et processorperspektiv er din hukommelse langsom. For at kompensere for forskellen i hastighed er der et par cacher indbygget i din processor (L1 / L2 cache). Så forestil dig, at du laver dine gode beregninger, og find ud af, at du har brug for et stykke hukommelse. Processoren får sin 'indlæsningsoperation' og indlæser hukommelsesstykket i cachen - og bruger derefter cachen til at udføre resten af ​​beregningerne. Fordi hukommelsen er relativt langsom, vil denne 'belastning' sænke dit program.
Ligesom grenforudsigelse blev dette optimeret i Pentium-processorer: processoren forudsiger, at den skal indlæse et stykke data og forsøger at indlæse det i cachen, før operationen rent faktisk rammer cachen. Som vi allerede har set, går forudsigelse af grene undertiden forfærdeligt galt - i værste fald skal du gå tilbage og faktisk vente på en hukommelsesbelastning, som vil tage for evigt (med andre ord: mislykket grenforudsigelse er dårlig, en hukommelse belastning efter at en forudsigelse af en filial forudsigelse er bare forfærdelig!
Heldigvis for os, hvis hukommelsesadgangsmønsteret er forudsigeligt, indlæser processoren det i sin hurtige cache, og alt er godt.
Den første ting, vi skal vide, er, hvad der er lille? Mens mindre generelt er bedre, er en tommelfingerregel at holde sig til opslagstabeller, der er <= 4096 bytes i størrelse. Som en øvre grænse: Hvis din opslagstabel er større end 64K, er det sandsynligvis værd at genoverveje.
Konstruktion af et bord
Så vi har fundet ud af, at vi kan skabe et lille bord. Den næste ting at gøre er at få en opslagsfunktion på plads. Opslagsfunktioner er normalt små funktioner, der bruger et par grundlæggende heltalstrin (og, eller, xor, skift, tilføj, fjern og måske gang). Du ønsker at få dine input oversat af opslagsfunktionen til en slags 'unik nøgle' ​​i din tabel, som derefter blot giver dig svaret på alt det arbejde, du ville have det til at udføre.
I dette tilfælde:> = 128 betyder, at vi kan beholde værdien, <128 betyder, at vi slipper af med den. Den nemmeste måde at gøre det på er ved at bruge et 'OG': hvis vi beholder det, OG vi det med 7FFFFFFF; hvis vi ønsker at slippe af med det, vi OG det med 0. Bemærk også, at 128 er en styrke på 2 - så vi kan gå videre og lave en tabel med 32768/128 heltal og udfylde det med et nul og en masse 7FFFFFFFF'er.
Administrerede sprog
Du undrer dig måske over, hvorfor dette fungerer godt på administrerede sprog. Når alt kommer til alt kontrollerer administrerede sprog grænserne for arrays med en gren for at sikre, at du ikke ødelægger ...
Nå, ikke ligefrem ... :-)
Der har været en del arbejde med at fjerne denne gren for administrerede sprog. For eksempel:
for (int i = 0; i  = 128)? c: 0;
}
// Test
DateTime startTime = System.DateTime.Now;
lang sum = 0;
for (int i = 0; i <100000; ++ i)
{
// Primær sløjfe
for (int j = 0; j  = 128. Det betyder, at vi let kan udtrække en enkelt bit, der fortæller os, om vi vil have en værdi eller ej: ved at skifte dataene til højre 7 bits, vi har en 0 bit eller en 1 bit, og vi vil kun tilføje værdien, når vi har en 1 bit. Lad os kalde denne bit "beslutningsbit".
Ved at bruge beslutningens bit 0/1 som et indeks i en matrix kan vi oprette kode, der vil være lige så hurtig, uanset om dataene sorteres eller ikke sorteres. Vores kode tilføjer altid en værdi, men når beslutningsbiten er 0, tilføjer vi værdien et eller andet sted, hvor vi ikke er interesserede. Her er koden:
// Test
clock_t start = ur ();
lang lang a [] = {0, 0};
lang lang sum
for (usigneret i = 0; i <100000; ++ i)
{
// Primær sløjfe
for (usigneret c = 0; c > 7);
a [j] + = data [c];
}
}
dobbelt elapsedTime = static_cast  (ur () - start) / CLOCKS_PER_SEC;
sum = a [1];
Denne kode spilder halvdelen af ​​tilføjelserne, men har aldrig en filforudsigelsesfejl. Det er enormt hurtigere på tilfældige data end versionen med en faktisk if-sætning.
Men i min testning var en eksplicit opslagstabel lidt hurtigere end dette, sandsynligvis fordi indeksering i en opslagstabel var lidt hurtigere end bitforskydning. Dette viser, hvordan min kode oprettes og bruger opslagstabellen (fantasifuldt kaldet lut for "LookUp Table" i koden). Her er C ++ -koden:
// Erklær og udfyld derefter opslagstabellen
int lut [256];
for (usigneret c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Brug opslagstabellen, når den er bygget
for (usigneret i = 0; i <100000; ++ i)
{
// Primær sløjfe
for (usigneret c = 0; c  værdi)
node = node-> pLeft;
andet
node = node-> pRight;
dette bibliotek ville gøre noget som:
i = (x  værdi);
node = node-> link [i];
Her er et link til denne kode: Red Black Trees, Eternally Confuzzled
|
I det sorterede tilfælde kan du gøre det bedre end at stole på en vellykket grenforudsigelse eller ethvert grenløst sammenligningstrick: Fjern grenen helt.
Faktisk er arrayet opdelt i en sammenhængende zone med data <128 og en anden med data> = 128. Så du skal finde partitionspunktet med en todelt søgning (ved hjælp af Lg (arraySize) = 15 sammenligninger), og derefter foretage en lige ophobning fra det punkt.
Noget som (ikke markeret)
int i = 0, j, k = arraySize;
mens (i > 1;
hvis (data [j]> = 128)
k = j;
andet
i = j;
}
sum = 0;
for (; i > 1;
for (i = 0, k = arraySize; i  = 128? k: i) = j)
j = (i + k) >> 1;
for (sum = 0; i  = 128)
/ \
/ \
/ \
sandt falsk
/ \
/ \
/ \
/ \
B) sum + = data [c]; C) til loop eller print ().
Uden grenforudsigelse ville følgende forekomme:
For at udføre instruktion B eller instruktion C bliver processoren nødt til at vente til instruktion A ikke når til EX-trin i rørledningen, da beslutningen om at gå til instruktion B eller instruktion C afhænger af resultatet af instruktion A. Så rørledningen vil se sådan ud.
når hvis betingelsen vender tilbage:
Når hvis betingelsen returnerer falsk:
Som et resultat af at vente på resultatet af instruktion A er de samlede CPU-cyklusser brugt i ovennævnte tilfælde (uden grenforudsigelse; for både sandt og falsk) 7.
Så hvad er gren forudsigelse?
Grenprediktor vil forsøge at gætte, hvilken vej en gren (en hvis-så-ellers-struktur) vil gå, før dette med sikkerhed er kendt. Det vil ikke vente på, at instruktionen A når EX-fasen af ​​rørledningen, men den vil gætte beslutningen og gå til den instruktion (B eller C i tilfælde af vores eksempel).
I tilfælde af et korrekt gæt, ser rørledningen sådan ud:
Hvis det senere opdages, at gæt var forkert, kasseres de delvist udførte instruktioner, og rørledningen starter forfra med den rigtige gren, hvilket medfører en forsinkelse.
Den tid, der spildes i tilfælde af en forkert forudsigelse af en gren, er lig med antallet af trin i rørledningen fra hentningstrinnet til udførelsestrinet. Moderne mikroprocessorer har tendens til at have ret lange rørledninger, så forsinkelsen af ​​forkert forudsigelse er mellem 10 og 20 urcyklusser. Jo længere rørledningen er, jo større er behovet for en god grenprædiktor.
I OP's kode, den første gang, når den betingede, har grenprædiktoren ingen oplysninger til at basere forudsigelse, så første gang vil den tilfældigt vælge den næste instruktion. Senere i for-sløjfen kan den basere forudsigelsen på historien.
For en matrix sorteret i stigende rækkefølge er der tre muligheder:
Alle elementerne er mindre end 128
Alle elementerne er større end 128
Nogle startende nye elementer er mindre end 128, og senere bliver de større end 128
Lad os antage, at forudsigeren altid vil antage den sande gren ved første løb.
Så i det første tilfælde vil det altid tage det sandegren siden historisk set alle dens forudsigelser er korrekte.
I 2. tilfælde forudsiger det oprindeligt forkert, men efter et par iterationer forudsiger det korrekt.
I det tredje tilfælde forudsiger det oprindeligt korrekt, indtil elementerne er mindre end 128. Derefter vil det mislykkes i nogen tid og det korrekte i sig selv, når det ser grenforudsigelsesfejl i historien.
I alle disse tilfælde vil fejlen være for mindre i antal, og som følge heraf er det kun et par gange nødvendigt at kassere de delvist udførte instruktioner og starte forfra med den rigtige gren, hvilket resulterer i færre CPU-cyklusser.
Men i tilfælde af et tilfældigt usorteret array skal forudsigelsen kaste de delvist udførte instruktioner og starte forfra med den rigtige gren det meste af tiden og resultere i flere CPU-cyklusser sammenlignet med det sorterede array.
|
Et officielt svar ville være fra
Intel - Undgå omkostningerne ved forkert forudsigelse af filialer
Intel - Branche- og loop-reorganisering for at forhindre urigtige forudsigelser
Videnskabelige papirer - gren forudsigelse computer arkitektur
Bøger: J.L. Hennessy, D.A. Patterson: Computerarkitektur: en kvantitativ tilgang
Artikler i videnskabelige publikationer: T.Y. Yeh, Y.N. Patt lavede mange af disse på grenforudsigelser.
Du kan også se fra dette dejlige diagram, hvorfor grenprediktoren bliver forvirret.
Hvert element i den oprindelige kode er en tilfældig værdi
data [c] = std :: rand ()% 256;
så forudsigeren skifter side, når std :: rand () blæser.
På den anden side, når først den er sorteret, vil forudsigeren først bevæge sig i en tilstand med stærkt ikke taget, og når værdierne skifter til den høje værdi, vil forudsigeren i tre løb gennemgå hele vejen fra stærkt ikke taget til stærkt taget.
|
I samme linje (jeg tror ikke dette blev fremhævet af noget svar) er det godt at nævne, at du nogle gange (specielt i software, hvor ydeevnen betyder noget - som i Linux-kernen), kan finde nogle, hvis udsagn som følgende:
hvis (sandsynligt (alt_is_ok))
{
/* Gør noget */
}
eller lignende:
hvis (usandsynligt (meget_improbabel_tilstand))
{
/* Gør noget */
}
Både sandsynligt () og usandsynligt () er faktisk makroer, der defineres ved hjælp af noget som GCC's __builtin_expect for at hjælpe kompilatoren med at indsætte forudsigelseskode for at favorisere tilstanden under hensyntagen til de oplysninger, der gives af brugeren. GCC understøtter andre indbyggede, der kan ændre opførelsen af ​​det kørende program eller udsende instruktioner på lavt niveau som at rydde cachen osv. Se denne dokumentation, der gennemgår de tilgængelige GCC's indbyggede.
Normalt findes denne form for optimeringer hovedsageligt i applikationer i realtid eller indlejrede systemer, hvor udførelsestid betyder noget, og det er kritisk. For eksempel, hvis du kontrollerer for en eller anden fejltilstand, der kun sker 1/10000000 gange, hvorfor så ikke informere compileren om dette? På denne måde antager grenforudsigelsen som standard, at betingelsen er falsk.
|
Ofte anvendte boolske operationer i C ++ producerer mange grene i det kompilerede program. Hvis disse grene er inde i sløjfer og er svære at forudsige, kan de nedsætte udførelsen betydeligt. Boolske variabler gemmes som 8-bit heltal med værdien 0 for falsk og 1 for sand.
Boolske variabler overbestemmes i den forstand, at alle operatører, der har boolske variabler som input, kontrollerer, om input har en anden værdi end 0 eller 1, men operatører, der har booleanske som output, kan ikke producere nogen anden værdi end 0 eller 1. Dette gør operationer med Boolske variabler som input er mindre effektive end nødvendigt.
Overvej eksempel:
bool a, b, c, d;
c = a && b;
d = a || b;
Dette implementeres typisk af compileren på følgende måde:
bool a, b, c, d;
hvis (a! = 0) {
hvis (b! = 0) {
c = 1;
}
andet {
til CFALSE;
}
}
andet {
CFALSE:
c = 0;
}
hvis (a == 0) {
hvis (b == 0) {
d = 0;
}
andet {
til DTRUE;
}
}
andet {
DTRUE:
d = 1;
}
Denne kode er langt fra optimal. Filialerne kan tage lang tid i tilfælde af misforudsigelser. De boolske operationer kan gøres meget mere effektive, hvis det med sikkerhed vides, at operanderne ikke har andre værdier end 0 og 1. Årsagen til, at kompilatoren ikke antager en sådan antagelse, er at variablerne kan have andre værdier, hvis de ikke er initialiseret eller kommer fra ukendte kilder. Ovenstående kode kan optimeres, hvis a og b er initialiseret til gyldige værdier, eller hvis de kommer fra operatører, der producerer boolsk output. Den optimerede kode ser sådan ud:
char a = 0, b = 1, c, d;
c = a & b;
d = a | b;
char bruges i stedet for bool for at gøre det muligt at bruge bitvis operatorer (& og |) i stedet for de boolske operatorer (&& og ||). De bitvise operatører er enkelt instruktioner, der kun tager en urcyklus. OR-operatøren (|) fungerer, selvom a og b har andre værdier end 0 eller 1. AND-operatoren (&) og EXKLUSIV ELLER-operatoren (^) kan give inkonsekvente resultater, hvis operanderne har andre værdier end 0 og 1.
~ kan ikke bruges til IKKE. I stedet,Du kan lave en boolsk IKKE på en variabel, der vides at være 0 eller 1 ved at XORere den med 1:
bool a, b;
b =! a;
kan optimeres til:
char a = 0, b;
b = a ^ 1;
a && b kan ikke erstattes med a & b, hvis b er et udtryk, der ikke skal evalueres, hvis a er falsk (&& vurderer ikke b, & vil). Ligeledes en || b kan ikke erstattes med a | b hvis b er et udtryk, der ikke skal evalueres, hvis a er sandt.
Brug af bitvise operatorer er mere fordelagtigt, hvis operanderne er variabler, end hvis operanderne er sammenligninger:
bool a; dobbelt x, y, z;
a = x> y && z <5,0;
er optimalt i de fleste tilfælde (medmindre du forventer, at &&-udtrykket genererer mange forkerte forudsigelser).
|
Det er sikkert!...
Gren forudsigelse gør logikken køre langsommere på grund af skiftet, der sker i din kode! Det er som om du går en lige gade eller en gade med mange vendinger, helt sikkert vil den lige blive gjort hurtigere! ...
Hvis matrixen sorteres, er din tilstand falsk i det første trin: data [c]> = 128, bliver derefter en sand værdi for hele vejen til slutningen af ​​gaden. Sådan kommer du hurtigere til slutningen af ​​logikken. På den anden side har du brug for en masse drejning og behandling ved hjælp af et usorteret array, der får din kode til at køre langsommere helt sikkert ...
Se på billedet, jeg oprettede for dig nedenfor. Hvilken gade skal færdiggøres hurtigere?
Så programmatisk får grenforudsigelse processen til at være langsommere ...
Også i slutningen er det godt at vide, at vi har to slags forudsigelser om, at hver vil påvirke din kode forskelligt:
1. Statisk
2. Dynamisk
Forudsigelse om statisk gren bruges af mikroprocessoren første gang
en betinget gren er stødt, og dynamisk gren forudsigelse er
bruges til efterfølgende udførelse af den betingede filialkode.
For effektivt at skrive din kode for at drage fordel af disse
regler, når du skriver if-else eller skifter udsagn, skal du kontrollere mest
almindelige sager først og arbejde gradvist ned til det mindst almindelige.
Sløjfer kræver ikke nødvendigvis nogen speciel bestilling af kode til
forudsigelse af statisk gren, som kun betingelsen for loop-iteratoren
bruges normalt.
|
Dette spørgsmål er allerede blevet besvaret fremragende mange gange. Alligevel vil jeg gerne henlede gruppens opmærksomhed på endnu en interessant analyse.
For nylig blev dette eksempel (meget modificeret) også brugt som en måde at demonstrere, hvordan et stykke kode kan profileres i selve programmet på Windows. Undervejs viser forfatteren også, hvordan man bruger resultaterne til at bestemme, hvor koden bruger det meste af sin tid i både den sorterede og usorterede sag. Endelig viser stykket også, hvordan man bruger et lidt kendt træk ved HAL (Hardware Abstraction Layer) til at bestemme, hvor meget misforudsigelse, der foregår i det usorterede tilfælde.
Linket er her:
En demonstration af selvprofilering
|
Som hvad der allerede er nævnt af andre, hvad der ligger bag mysteriet er Branch Predictor.
Jeg prøver ikke at tilføje noget, men forklarer konceptet på en anden måde.
Der er en kort introduktion på wiki, der indeholder tekst og diagram.
Jeg kan godt lide forklaringen nedenfor, der bruger et diagram til at uddybe grenprediktoren intuitivt.
I computerarkitektur er en grenprædiktor en
digitalt kredsløb, der forsøger at gætte hvilken vej en gren (f.eks. en
hvis-så-ellers-struktur) vil gå, før dette med sikkerhed er kendt. Det
Formålet med grenprediktoren er at forbedre strømmen i
instruktionsrørledning. Grenprædiktorer spiller en kritisk rolle i
opnå høj effektiv ydeevne i mange moderne rørledninger
mikroprocessorarkitekturer såsom x86.
To-vejs forgrening implementeres normalt med et betinget spring
instruktion. Et betinget spring kan enten "ikke tages" og fortsætte
udførelse med den første gren af ​​koden, der følger straks
efter det betingede spring, eller det kan "tages" og hoppe til en
andet sted i programhukommelsen, hvor den anden gren af ​​koden er
gemt. Det vides ikke med sikkerhed, om et betinget spring vil være
taget eller ikke taget, før tilstanden er beregnet, og
betinget spring har bestået eksekveringsfasen i instruktionen
rørledning (se fig. 1).
Baseret på det beskrevne scenario har jeg skrevet en animationsdemo for at vise, hvordan instruktioner udføres i en pipeline i forskellige situationer.
Uden filialforudsigeren.
Uden filialforudsigelse ville processoren være nødt til at vente til
betinget springinstruktion har bestået udførelsestrinet før
næste instruktion kan komme ind i hentningstrinnet i pipelinen.
Eksemplet indeholder tre instruktioner, og den første er en betinget springinstruktion. De sidstnævnte to instruktioner kan gå i rørledningen, indtil den betingede springinstruktion udføres.
Det tager 9 urcyklusser, før 3 instruktioner er afsluttet.
Brug Branch Predictor og tag ikke et betinget spring. Lad os antage, at forudsigelsen ikke tagerbetinget spring.
Det tager 7 urcyklusser, før 3 instruktioner er afsluttet.
Brug Branch Predictor og tag et betinget spring. Lad os antage, at forudsigelsen ikke tager det betingede spring.
Det tager 9 urcyklusser, før 3 instruktioner er afsluttet.
Den tid, der spildes i tilfælde af en forkert forudsigelse af en gren, er lig med
antallet af trin i rørledningen fra hentningstrinnet til
udføre etape. Moderne mikroprocessorer har tendens til at have ret lang tid
rørledninger, så forsinkelsen af ​​forkert forudsigelse er mellem 10 og 20 ur
cyklusser. Som et resultat øger behovet for en at gøre en pipeline længere
mere avanceret gren forudsigelse.
Som du kan se, ser det ud til, at vi ikke har en grund til ikke at bruge Branch Predictor.
Det er en ganske enkel demo, der præciserer den meget grundlæggende del af Branch Predictor. Hvis disse gifs er irriterende, er du velkommen til at fjerne dem fra svaret, og besøgende kan også få live demo-kildekoden fra BranchPredictorDemo
|
Forudsigelsesgevinst på gren!
Det er vigtigt at forstå, at misforudsigelse på grene ikke bremser programmerne. Omkostningerne ved en ubesvaret forudsigelse er ligesom om forudsigelse af grenen ikke eksisterede, og du ventede på, at udtrykket skulle vurderes, hvilken kode der skulle køres (yderligere forklaring i næste afsnit).
hvis (udtryk)
{
// Kør 1
} andet {
// Kør 2
}
Når der er en if-else \ switch-sætning, skal udtrykket evalueres for at bestemme, hvilken blok der skal udføres. I samlingskoden, der genereres af kompilatoren, indsættes betingede greninstruktioner.
En greninstruktion kan få en computer til at begynde at udføre en anden instruktionssekvens og således afvige fra dens standardopførsel ved at udføre instruktioner i rækkefølge (dvs. hvis udtrykket er falsk, springer programmet over koden til if-blokken) afhængigt af en eller anden tilstand er udtryksvurderingen i vores sag.
Når det er sagt, forsøger compileren at forudsige resultatet, før det faktisk bliver evalueret. Det henter instruktioner fra if-blokken, og hvis udtrykket viser sig at være sandt, så vidunderligt! Vi fik den tid, det tog at evaluere det og gjorde fremskridt med koden; hvis ikke, kører vi den forkerte kode, rørledningen skylles, og den korrekte blok køres.
Visualisering:
Lad os sige, at du skal vælge rute 1 eller rute 2. Venter på, at din partner kontrollerer kortet, du er stoppet ved ## og ventede, eller du kunne bare vælge rute1, og hvis du var heldig (rute 1 er den rigtige rute), så dejligt, du behøvede ikke at vente på, at din partner kontrollerede kortet (du sparede den tid, det ville have taget ham at kontrollere kortet), ellers vender du bare tilbage.
Mens skylning af rørledninger er super hurtig, er det i dag det værd at tage denne gamble. Forudsigelse af sorterede data eller data, der ændrer sig langsomt, er altid nemmere og bedre end at forudsige hurtige ændringer.
O Rute 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
Rute 2 \ --------------------------------
|
På ARM er der ingen filial nødvendig, fordi hver instruktion har et 4-bit tilstandsfelt, der tester (til nul pris) nogen af ​​16 forskellige forskellige betingelser, der kan opstå i Processor Status Register, og hvis betingelsen på en instruktion er falsk, instruktionerne springes over. Dette eliminerer behovet for korte grene, og der ville ikke være nogen gren forudsigelse hit for denne algoritme. Derfor vil den sorterede version af denne algoritme køre langsommere end den usorterede version på ARM på grund af den ekstra omkostning ved sortering.
Den indre sløjfe for denne algoritme vil se ud som følgende på ARM-samlingssprog:
MOV R0, # 0 // R0 = sum = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, data // R2 = addr af dataarray (sæt denne instruktion uden for ydre sløjfe)
.inner_loop // Etiket for gren af ​​indre sløjfe
LDRB R3, [R2, R1] // R3 = data [c]
CMP R3, # 128 // sammenlign R3 med 128
TILFØJ R0, R0, R3 // hvis R3> = 128, så sum + = data [c] - ingen gren nødvendig!
TILFØJ R1, R1, # 1 // c ++
CMP R1, #arraySize // sammenlign c med arraySize
BLT inner_loop // Forgren til inner_loop hvis c  ());
for (usigneret c = 0; c  = 128
sum = sum + data1 (j);
ende
ende
ende
toc;
ExeTimeWithSorting = toc - tic;
Resultaterne for ovenstående MATLAB-kode er som følger:
a: Forløbet tid (uden sortering) = 3479.880861 sekunder.
b: Forløbet tid (med sortering) = 2377.873098 sekunder.
Resultaterne af C-koden som i @GManNickG får jeg:
a: Forløbet tid (uden sortering) = 19,8761 sek.
b: Forløbet tid (med sortering) = 7.37778 sek.
Baseret på dette ser det ud til, at MATLAB er næsten 175 gange langsommere end C-implementeringen uden sortering og 350 gange langsommere med sortering. Med andre ord er effekten (af forudsigelse af grene) 1,46x for MATLAB-implementering og 2,7x for C-implementeringen.
|
Antagelsen fra andre svar om, at man har brug for at sortere dataene, er ikke korrekt.
Den følgende kode sorterer ikke hele arrayet, men kun segmenter med 200 element, og kører derved hurtigst.
Sortering af kun k-element sektioner fuldender forbehandlingen i lineær tid, O (n), snarere end den O (n.log (n)) tid, der er nødvendig for at sortere hele arrayet.
# inkluderer 
# inkluderer 
# inkluderer 
int main () {
int-data [32768]; const int l = størrelse af data / størrelse af data [0];
for (usigneret c = 0; c  = 128)
sum + = data [c];
}
}
std :: cout << static_cast  (clock () - start) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "sum =" << sum << std :: endl;
}
Dette "beviser" også, at det ikke har noget at gøre med noget algoritmisk problem såsom sorteringsrækkefølge, og det er faktisk grenforudsigelse.
|
Bjarne Stroustrups svar på dette spørgsmål:
Det lyder som et interviewspørgsmål. Er det sandt? Hvordan ville du vide det? Det er en dårlig idé at besvare spørgsmål om effektivitet uden først at foretage nogle målinger, så det er vigtigt at vide, hvordan man måler.
Så jeg prøvede med en vektor på en million heltal og fik:
Allerede sorteret 32995 millisekunder
Blandet 125944 millisekunder
Allerede sorteret 18610 millisekunder
Blandet 133304 millisekunder
Allerede sorteret 17942 millisekunder
Blandet 107858 millisekunder
Jeg løb det et par gange for at være sikker. Ja, fænomenet er ægte. Min nøglekode var:
ugyldig kørsel (vektor  & v, const streng & label)
{
auto t0 = systemur :: nu ();
sorter (v.begin (), v.end ());
auto t1 = systemur :: nu ();
cout << label
<< duration_cast  (t1 - t0) .count ()
<< "millisekunder \ n";
}
ugyldig tst ()
{
vektor  v (1'000'000);
iota (v.begin (), v.end (), 0);
kør (v, "allerede sorteret");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
køre (v, "blandet");
}
I det mindste er fænomenet ægte med denne compiler, standardbibliotek og optimeringsindstillinger. Forskellige implementeringer kan og giver forskellige svar. Faktisk gjorde nogen en mere systematisk undersøgelse (en hurtig websøgning finder den), og de fleste implementeringer viser den effekt.
En af årsagerne er grenforudsigelse: nøgleoperationen i sorteringsalgoritmen er "if (v [i]  = 128. Det betyder, at vi let kan udtrække en enkelt bit, der fortæller os, om vi vil have en værdi eller ej: ved at skifte dataene til højre 7 bits, vi har en 0 bit eller en 1 bit, og vi vil kun tilføje værdien, når vi har en 1 bit. Lad os kalde denne bit "beslutningsbit".
Ved at bruge beslutningens bit 0/1 som et indeks i en matrix kan vi oprette kode, der vil være lige så hurtig, uanset om dataene sorteres eller ikke sorteres. Vores kode tilføjer altid en værdi, men når beslutningsbiten er 0, tilføjer vi værdien et eller andet sted, hvor vi ikke er interesserede. Her er koden:
// Test
clock_t start = ur ();
lang lang a [] = {0, 0};
lang lang sum
for (usigneret i = 0; i <100000; ++ i)
{
// Primær sløjfe
for (usigneret c = 0; c > 7);
a [j] + = data [c];
}
}
dobbelt elapsedTime = static_cast  (ur () - start) / CLOCKS_PER_SEC;
sum = a [1];
Denne kode spilder halvdelen af ​​tilføjelserne, men har aldrig en filforudsigelsesfejl. Det er enormt hurtigere på tilfældige data end versionen med en faktisk if-sætning.
Men i min testning var en eksplicit opslagstabel lidt hurtigere end dette, sandsynligvis fordi indeksering i en opslagstabel var lidt hurtigere end bitforskydning. Dette viser, hvordan min kode oprettes og bruger opslagstabellen (fantasifuldt kaldet lut for "LookUp Table" i koden). Her er C ++ -koden:
// Erklær og udfyld derefter opslagstabellen
int lut [256];
for (usigneret c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Brug opslagstabellen, når den er bygget
for (usigneret i = 0; i <100000; ++ i)
{
// Primær sløjfe
for (usigneret c = 0; c  værdi)
node = node-> pLeft;
andet
node = node-> pRight;
dette bibliotek ville gøre noget som:
i = (x  værdi);
node = node-> link [i];
Det er en god løsning, og måske fungerer den.
|
Meget aktivt spørgsmål. Optjen 10 omdømme for at besvare dette spørgsmål. Omdømmekravet hjælper med at beskytte dette spørgsmål mod spam og ikke-svar-aktivitet.
Er det ikke det svar, du leder efter? Gennemse andre spørgsmål mærket java c ++ ydeevneoptimering gren-forudsigelse eller stil dit eget spørgsmål.